package QuestionDaily;

import java.util.Arrays;

public class maxSumOfThreeSubarrays_689 {
    /**
     * 找出三个长度为 k 、互不重叠、且全部数字和（3 * k 项）最大的子数组
     * 以下标的数组形式返回结果，数组中的每一项分别指示每个子数组的起始位置（下标从 0 开始）。
     * 如果有多个结果，返回字典序最小的一个。
     * @param nums 1 <= nums[i] < 216
     * @param k
     * @return
     */
    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        /**
         * 思路是，既然是全部的数字和，
         * 遍历得到每一个位置作为子数组结尾时的数位和
         * 再进行处理
         * 思路没能成功
         */
        int[] arr=new int[nums.length];
        int sum=0;
        //算出每个k大小的连续区域的数位和
        for(int i=0;i< nums.length;i++){
            if(i<k-1){
                sum+=nums[i];  //前k-1位不可能是区域最后一位数字，计算和
            } else if(i>k-1) {
                arr[i]=sum+nums[i]-nums[i-k];  //加上当前数的数位和，去掉最前面的数位和
            }else {
                arr[i]=sum+nums[i];
            }
        }
        return arr;
    }



    /**
     * 总体方向也是滑动窗口
     * 多个滑动窗口并行滑动处理
     * @param nums
     * @param k
     * @return
     */
    public int[] maxSumOfThreeSubarrays2(int[] nums, int k) {
        /**
         * 使用三个大小为 k 的滑动窗口。
         * 设 sum1为第一个滑动窗口的元素和，该滑动窗口从 [0,k−1]开始；
         * sum2为第二个滑动窗口的元素和，该滑动窗口从 [k,2k−1]开始；
         * sum3为第三个滑动窗口的元素和，该滑动窗口从 [2k,3k−1]开始。
         */
        int[] ans = new int[3];
        int sum1 = 0, maxSum1 = 0, maxSum1Idx = 0;//维护 sum1的最大值 maxSum1及其对应位置
        int sum2 = 0, maxSum12 = 0, maxSum12Idx1 = 0, maxSum12Idx2 = 0; //这一过程中的 maxSum1+sum2的最大值（记作 maxSum12 ）及其对应位置。
        int sum3 = 0, maxTotal = 0;
        for (int i = k * 2; i < nums.length; ++i) {
            sum1 += nums[i - k * 2];  //三个窗口同时向右增添数字
            sum2 += nums[i - k];
            sum3 += nums[i];
            if (i >= k * 3 - 1) {
                if (sum1 > maxSum1) {  //窗口1，新的窗口数字和大于之前的窗口数字和最大值，进行更新
                    maxSum1 = sum1;
                    maxSum1Idx = i - k * 3 + 1;
                }
                if (maxSum1 + sum2 > maxSum12) { //窗口1和窗口2的和大于之前的max值，进行更新
                    maxSum12 = maxSum1 + sum2;
                    maxSum12Idx1 = maxSum1Idx;
                    maxSum12Idx2 = i - k * 2 + 1;
                }
                if (maxSum12 + sum3 > maxTotal) {   //窗口1，2，3的和大于之前的max值，进行更新
                    maxTotal = maxSum12 + sum3;
                    ans[0] = maxSum12Idx1;
                    ans[1] = maxSum12Idx2;
                    ans[2] = i - k + 1;
                }
                sum1 -= nums[i - k * 3 + 1];
                sum2 -= nums[i - k * 2 + 1];
                sum3 -= nums[i - k + 1]; //删除窗口左边的数字，滑动完成
            }
        }
        return ans;
    }
}
